package com.zx._12_算法.剑指offer._2022;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/
 */
public class 和为s的连续正数序列 {

    public static void main(String[] args) {
        findContinuousSequence2(9);
    }

    public static int[][] findContinuousSequence2(int target) {
        List<int[]> res = new ArrayList<>();

        for (int i = 1; i < target / 2 + 1; i++) {
            // 元素第一个值
            int begin = i;

            // j是元素个数
            for (int j = 2; j < target / 2 + 1; j++) {
                int[] item = new int[j];
                int sum = 0;

                for (int k = 0; k < j; k++) {
                    item[k] = begin + k;
                    sum += item[k];
                }
                if (sum == target) {
                    res.add(item);
                } else if (sum > target) {
                    break;
                }

            }
        }

        return res.toArray(new int[res.size()][]);
    }

    public int[][] findContinuousSequence1(int target) {
        List<int[]> res = new ArrayList<>();
        for (int i = 2; i < target / 2; i++) {
            // 数组的数量
            int size = i;
            int begin = 1;
            int end = target - 1;
            for (int j = begin; j < end; j++) {
                int sum = 0;
                int[] item = new int[size];

                int idx = 0;
                for (int k = j; k < j + size; k++) {
                    item[idx] = k;
                    idx++;
                    sum += k;
                }
                if (sum == target) {
                    res.add(item);
                }
            }
        }
        return res.toArray(new int[res.size()][]);
    }

    public int[][] findContinuousSequence3(int target) {
        List<int[]> res = new ArrayList<>();

        // 数据全部的枚举
        int[] data = new int[target / 2 + 1];
        for (int i = 0; i < data.length; i++) {
            data[i] = i + 1;
        }

        for (int i = 0; i < data.length; i++) {
            // 开始结束2个符合调整数组的索引
            int begin = i;
            int end = 0;

            int sum = 0;

            for (int j = i; j < data.length; j++) {
                sum += data[j];
                if (sum == target) {
                    end = j;
                    res.add(Arrays.copyOfRange(data, begin, end));
                    break;
                } else if (sum > target) {
                    break;
                }
            }

        }

        return res.toArray(new int[res.size()][]);
    }
}
